GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Miller-Rabin-Test</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Miller-Rabin-Test</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Miller-Rabin-Test oder Miller-Selfridge-Rabin-Test (kurz MRT) ist ein <a href="Randomisierter_Algorithmus" title="Randomisierter Algorithmus">probabilistischer</a> <a href="Primzahltest" title="Primzahltest">Primzahltest</a> und damit ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> aus dem <a href="Teilgebiete_der_Mathematik" title="Teilgebiete der Mathematik">mathematischen Teilgebiet</a> <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a>, insbesondere der <a href="Algorithmische_Zahlentheorie" title="Algorithmische Zahlentheorie">algorithmischen Zahlentheorie</a>.

Der MRT erhält als Eingabe eine <a href="Parit%C3%A4t_(Mathematik)" title="Parität (Mathematik)">ungerade</a> <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürliche Zahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq 5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a752e15bfe1dac8d617d014a77c275bfd4af0d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 5}" loading="lazy">, von der man wissen will, ob sie prim ist, und eine weitere Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in \{2,3,4,\dotsc ,n-2\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in \{2,3,4,\dotsc ,n-2\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b06bcc69f738aadb256c61784243da546894f2fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.526ex; height:2.843ex;" alt="{\displaystyle a\in \{2,3,4,\dotsc ,n-2\}}" loading="lazy"> und gibt entweder „zusammengesetzt“ oder „wahrscheinlich prim“ aus. Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> prim, so lautet die Ausgabe immer „wahrscheinlich prim“. Anderenfalls wird in den meisten Fällen „zusammengesetzt“ ausgegeben, aber für manche Paare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n,a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n,a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65f10f65fcba30f32673bd2ffe9f8e006f5a624b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.658ex; height:2.009ex;" alt="{\displaystyle n,a}" loading="lazy"> mit <a href="Zusammengesetzte_Zahl" title="Zusammengesetzte Zahl">zusammengesetztem</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist die Ausgabe trotzdem „wahrscheinlich prim“.

Oft wird <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> <a href="Zufallszahl" title="Zufallszahl">zufällig</a> gewählt, der MRT zählt in dieser Form zur Klasse der <a href="Monte-Carlo-Algorithmus" title="Monte-Carlo-Algorithmus">Monte-Carlo-Algorithmen</a>. Durch wiederholtes Testen mit verschiedenen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> kann die Wahrscheinlichkeit eines Irrtums beliebig klein gehalten werden. Es gibt <a href="#Deterministische_Varianten">deterministische Varianten</a> des MRT, bei denen durch geeignete Wahl der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein Irrtum ausgeschlossen wird.

Der MRT ist nach <a href="Gary_L._Miller" title="Gary L. Miller">Gary L. Miller</a> und <a href="Michael_O._Rabin" title="Michael O. Rabin">Michael O. Rabin</a> benannt.<a href="#cite_note-1">[1]</a> <a href="John_L._Selfridge" title="John L. Selfridge">John L. Selfridge</a> hat diesen Test schon 1974 verwendet, bevor Rabin ihn 1976 veröffentlichte. Daher rührt der alternative Name Miller-Selfridge-Rabin-Test.<a href="#cite_note-YAN-2">[2]</a>

Der MRT funktioniert ähnlich wie der <a href="Solovay-Strassen-Test" title="Solovay-Strassen-Test">Solovay-Strassen-Test</a>, ist diesem allerdings in allen Aspekten überlegen. Er ist schneller, seine Irrtumswahrscheinlichkeit ist geringer, und alle Paare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, für die der Solovay-Strassen-Test die richtige Ausgabe liefert, werden auch vom MRT richtig erkannt.

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

Es sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine <a href="Ungerade_Zahl" class="mw-redirect" title="Ungerade Zahl">ungerade Zahl</a>, von der festgestellt werden soll, ob sie eine Primzahl ist. Zuerst berechnet man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> (ungerade) so, dass

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1=2^{j}\cdot d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a93a44b8c9984528af542745c070b0c550bca7cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.463ex; height:2.843ex;" alt="{\displaystyle n-1=2^{j}\cdot d}" loading="lazy">.</dd></dl>

Dann wählt man eine Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> aus der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{2,3,\dotsc ,n-2\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{2,3,\dotsc ,n-2\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6de8e97627c8d9340622626bb8878c97c8534917.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.26ex; height:2.843ex;" alt="{\displaystyle \{2,3,\dotsc ,n-2\}}" loading="lazy">.

Der nächste Schritt ist ein Test, den nur Primzahlen und <a href="Starke_Pseudoprimzahl" title="Starke Pseudoprimzahl">starke Pseudoprimzahlen</a> (zur Basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">) bestehen: Man prüft, ob entweder

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{d}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fbd85b469a4bd1028f98a9ba2a0a9e170006f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.661ex; height:3.176ex;" alt="{\displaystyle a^{d}\equiv 1{\pmod {n}}}" loading="lazy"></dd></dl>

oder

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/358e96898dfe43d19e90b9f02d26993c0d8aa275.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.515ex; height:3.176ex;" alt="{\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}" loading="lazy"> für ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq r<j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq r<j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c8e0d159557cac2b14689c13d7c7b457193ed0f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.366ex; height:2.509ex;" alt="{\displaystyle 0\leq r<j}" loading="lazy"></dd></dl>

gilt. Für eine Primzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist dies stets der Fall.

Wenn die Bedingung nicht erfüllt ist, muss also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> zusammengesetzt sein. Die Bedingung wird jedoch auch von einigen Zahlenpaaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> mit zusammengesetztem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> erfüllt, so dass der Test die Zusammengesetztheit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> mit diesem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> nicht zeigt. Dann heißt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine starke Pseudoprimzahl zur Basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2></div>

Man betrachtet die Folge

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a^{d},a^{2d},a^{4d},\ldots ,a^{2^{j-1}d},a^{2^{j}d})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/10b2276abdad32f92f728682a3c5cd4da4f66a2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.12ex; height:3.509ex;" alt="{\displaystyle (a^{d},a^{2d},a^{4d},\ldots ,a^{2^{j-1}d},a^{2^{j}d})}" loading="lazy">,</dd></dl>

In der jedes Element das Quadrat seines Vorgängers ist. Die Elemente werden <a href="Division_mit_Rest#Modulo" title="Division mit Rest">modulo</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> berechnet.

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine Primzahl, dann gilt nach dem <a href="Kleiner_fermatscher_Satz" title="Kleiner fermatscher Satz">kleinen fermatschen Satz</a>

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2^{j}d}=a^{n-1}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e70b81f292062a9336f9411a44d19655800f6d27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.845ex; height:3.509ex;" alt="{\displaystyle a^{2^{j}d}=a^{n-1}\equiv 1{\pmod {n}}}" loading="lazy"></dd></dl>

und obige Folge hat deshalb 1 als letztes Element.

Für Primzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist der Vorgänger einer 1 in der Folge immer kongruent zu 1 oder zu −1:

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}x^{2}\equiv 1{\pmod {n}}&\Leftrightarrow x^{2}-1\equiv 0{\pmod {n}}\\&\Leftrightarrow n|x^{2}-1\\&\Leftrightarrow n|(x-1)(x+1)\\&\Leftrightarrow n|(x-1)\quad {\text{oder}}\quad n|(x+1)\\&\Leftrightarrow x-1\equiv 0{\pmod {n}}\quad {\text{oder}}\quad x+1\equiv 0{\pmod {n}}\\&\Leftrightarrow x\equiv 1{\pmod {n}}\quad {\text{oder}}\quad x\equiv -1{\pmod {n}}\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/698f8548e74c48ea67cf2300c32573fc13cd6762.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.005ex; width:72.478ex; height:19.176ex;" alt="{\displaystyle {\begin{aligned}x^{2}\equiv 1{\pmod {n}}&\Leftrightarrow x^{2}-1\equiv 0{\pmod {n}}\\&\Leftrightarrow n|x^{2}-1\\&\Leftrightarrow n|(x-1)(x+1)\\&\Leftrightarrow n|(x-1)\quad {\text{oder}}\quad n|(x+1)\\&\Leftrightarrow x-1\equiv 0{\pmod {n}}\quad {\text{oder}}\quad x+1\equiv 0{\pmod {n}}\\&\Leftrightarrow x\equiv 1{\pmod {n}}\quad {\text{oder}}\quad x\equiv -1{\pmod {n}}\\\end{aligned}}}" loading="lazy"></dd></dl>

Die Folge besteht dann also entweder nur aus Einsen, oder sie enthält <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> (was sich bei modulo-n-Rechnung für einen Wert kongruent zu −1 ergibt), worauf wegen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-1)^{2}\equiv 1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)^{2}\equiv 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1803d7763b68051e708b25b617dd4c2617264b8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.522ex; height:3.176ex;" alt="{\displaystyle (n-1)^{2}\equiv 1}" loading="lazy"> Einsen folgen. Wenn die Folge nicht diese Form hat, muss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> zusammengesetzt sein.

Man prüft, ob die Folge mit 1 beginnt oder ob <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> spätestens als vorletztes Element auftritt. Ist dies der Fall, ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> entweder prim oder eine starke Pseudoprimzahl zur Basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, und es wird „möglicherweise prim“ ausgegeben. Ansonsten kann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nicht prim sein, und der Algorithmus gibt „zusammengesetzt“ aus. Man kann die Berechnung abbrechen, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> oder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> ohne vorhergehendes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> auftritt, denn danach kann nur noch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> kommen.

<div class="mw-heading mw-heading2"><h2 id="Zuverlässigkeit">Zuverlässigkeit</h2></div>

Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq 5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a752e15bfe1dac8d617d014a77c275bfd4af0d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 5}" loading="lazy"> ungerade und nicht prim, so enthält die Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{2,3,\ldots ,n-2\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{2,3,\ldots ,n-2\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd0f27338ee60f5e7719d4368fe9d0ed00dc1399.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.26ex; height:2.843ex;" alt="{\displaystyle \{2,3,\ldots ,n-2\}}" loading="lazy"> höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n-3}{4}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n-3}{4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67114047866604fbe92d4c27da94f7ad342c724d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.923ex; height:3.676ex;" alt="{\displaystyle {\tfrac {n-3}{4}}}" loading="lazy"> Elemente <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {ggT} (a,n)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {ggT} (a,n)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da94fb616de1f14fbf0fe6d742a1dd9e79aaf463.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.732ex; height:2.843ex;" alt="{\displaystyle \operatorname {ggT} (a,n)=1}" loading="lazy">, die keine Zeugen für die Zusammengesetztheit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> sind. Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g=\operatorname {ggT} (a,n)>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g=\operatorname {ggT} (a,n)>1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5f77bda074794362caa1d61e6ed21ef8157844d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.946ex; height:2.843ex;" alt="{\displaystyle g=\operatorname {ggT} (a,n)>1}" loading="lazy">, dann wird immer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{x}\equiv kg{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{x}\equiv kg{\pmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cacd85c5eaf23c76cb8e8540904bedc133900129.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.907ex; height:2.843ex;" alt="{\displaystyle a^{x}\equiv kg{\pmod {n}}}" loading="lazy"> für ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a5bc4b7383031ba693b7433198ead7170954c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.73ex; height:2.176ex;" alt="{\displaystyle k\in \mathbb {N} }" loading="lazy"> sein, und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> wird als zusammengesetzt erkannt.

Ist ein zusammengesetztes ungerades <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gegeben und wählt man zufällig ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{2,3,\ldots ,n-2\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{2,3,\ldots ,n-2\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd0f27338ee60f5e7719d4368fe9d0ed00dc1399.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.26ex; height:2.843ex;" alt="{\displaystyle \{2,3,\ldots ,n-2\}}" loading="lazy">, dann ist somit die <a href="Wahrscheinlichkeit" title="Wahrscheinlichkeit">Wahrscheinlichkeit</a>, dass das Ergebnis „wahrscheinlich prim“ lautet, kleiner als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{4}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4825cd2a1ca51dfc4d53042434f6d3733370a57f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{4}}}" loading="lazy">.

Wiederholt man den Test mehrfach für verschiedene voneinander unabhängig gewählte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> aus dieser Menge, sinkt die Wahrscheinlichkeit weiter ab. Nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> Schritten ist die Wahrscheinlichkeit, eine zusammengesetzte Zahl für prim zu halten, kleiner als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\tfrac {1}{4}})^{s}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\tfrac {1}{4}})^{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e47e23a87f612701f28e5874decf1a9ce780453b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:4.471ex; height:3.509ex;" alt="{\displaystyle ({\tfrac {1}{4}})^{s}}" loading="lazy">, also z. B. nach vier Schritten kleiner als 0,4 % und nach zehn Schritten kleiner als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 10^{-6}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10^{-6}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70b5788b8e24bbc50c5c6fc7b5ef4953cb2291e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.658ex; height:2.676ex;" alt="{\displaystyle 10^{-6}}" loading="lazy">.

Das ist eine pessimistische Schätzung, die von den „problematischsten“ Werten für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ausgeht. Für die meisten zusammengesetzten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist der Anteil der Basen, die ein falsches Ergebnis liefern, erheblich kleiner als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{4}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{4}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4825cd2a1ca51dfc4d53042434f6d3733370a57f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{4}}}" loading="lazy">, und für viele ist er sogar 0.

<div class="mw-heading mw-heading2"><h2 id="Deterministische_Varianten">Deterministische Varianten</h2></div>

Der Miller-Rabin-Algorithmus kann deterministisch angewendet werden, indem alle Basen in einer bestimmten Menge getestet werden (Beispiel: wenn n < 9.080.191, dann ist es ausreichend a = 31 und 73 zu testen, siehe unten).

Wenn das getestete <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> zusammengesetzt ist, sind diejenigen zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> teilerfremden Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">, die keine Zeugen für die Zusammengesetztheit von n sind, in einer echten <a href="Untergruppe" title="Untergruppe">Untergruppe</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}">

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ddd09edf84313d00dc4680434975dd3f1288919d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.521ex; height:3.009ex;" alt="{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}" loading="lazy"> enthalten. Dies bedeutet, dass beim Testen aller <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> aus einer Menge, die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}">

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ddd09edf84313d00dc4680434975dd3f1288919d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.521ex; height:3.009ex;" alt="{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}" loading="lazy"> erzeugt, eines der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> ein Zeuge für das Zusammengesetztsein von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist. Wenn angenommen wird, dass die <a href="Riemannsche_Vermutung" title="Riemannsche Vermutung">Riemannsche Vermutung</a> wahr ist, dann folgt daraus, dass die Gruppe durch ihre Elemente kleiner O((log n)2) generiert wird, was bereits im <a href="Algorithmus_von_Miller" title="Algorithmus von Miller">Algorithmus von Miller</a> angeführt wurde.<a href="#cite_note-miller-3">[3]</a> Die Konstante in der <a href="Landau-Symbole" title="Landau-Symbole">Landau-Notation</a> wurde von Eric Bach auf 2 reduziert.<a href="#cite_note-4">[4]</a>

Deshalb erhält man einen deterministischen Primzahltest, wenn alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in \{2,\ldots ,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in \{2,\ldots ,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e9e01b23e3abfcf450f6901a151a10f98ea2c43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.664ex; height:3.176ex;" alt="{\displaystyle a\in \{2,\ldots ,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )\}}" loading="lazy"> getestet werden. Die Laufzeit dieses Algorithmus ist O((log n)4).

Wenn die Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> klein ist, ist es nicht notwendig, alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(\ln n)^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(\ln n)^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/66c0c1eb00a69a3e5571fcb3a416ee124e6c0380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.747ex; height:3.176ex;" alt="{\displaystyle 2(\ln n)^{2}}" loading="lazy"> zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist.

Beispielsweise wurde folgendes verifiziert:

<th>n kleiner als</th>

<th>zu testende a</th>

<th>Quelle

</th></tr>

<tr>

</td></tr>

<tr>

<td>2, 3

</td></tr>

<tr>

</td></tr>

<tr>

<td>2, 7, 61

</td></tr>

<tr>

</td></tr>

<tr>

<td>2, 3, 5, 7, 11, 13

</td></tr>

<tr>

<td>2, 3, 5, 7, 11, 13, 17

</td></tr>

<tr>

</td></tr>

<tr>

</td></tr>

<tr>

<td>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41

</td></tr></tbody></table>

Dabei dürfen nur solche <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> getestet werden, die größer sind als das jeweils größte angegebene <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy">.

Für das letzte Beispiel ist die Schranke <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\leq \lfloor 2\cdot (\ln n)^{2}\rfloor =6325}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\leq \lfloor 2\cdot (\ln n)^{2}\rfloor =6325}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d39d62ca084289aabb63c57f27d3351ec9bb6152.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.568ex; height:3.176ex;" alt="{\displaystyle a\leq \lfloor 2\cdot (\ln n)^{2}\rfloor =6325}" loading="lazy">. Daran ist zu erkennen, wie viel eingespart wird, indem nur die Primzahlen bis 41 verwendet werden.

Siehe auch die Prime Pages,<a href="#cite_note-12">[9]</a> Miller-Rabin SPRP bases records,<a href="#cite_note-13">[10]</a> Zhang/Tang<a href="#cite_note-14">[11]</a> und ebenso die Folge A014233<a href="#cite_note-15">[12]</a> in <a href="OEIS" class="mw-redirect" title="OEIS">OEIS</a> zu anderen Kriterien ähnlicher Art. Auf diese Weise hat man sehr schnelle deterministische Primzahltests für Zahlen im geeigneten Bereich, ohne auf unbewiesene Annahmen zurückgreifen zu müssen.

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

Diese <a href="C%2B%2B" title="C++">C++</a>-Implementierung kann alle Zahlen kleiner <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{32}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{32}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8c222ea8e5f187a2bb499395b6f4a6f38b43633.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.039ex; height:2.676ex;" alt="{\displaystyle 2^{32}}" loading="lazy"> behandeln:

<div class="mw-highlight mw-highlight-lang-c++ mw-content-ltr" dir="ltr"><pre>#include <cstdint>

using u32 = std::uint32_t;

using u64 = std::uint64_t;

bool wahrscheinlich_prim(const u32 n, const u32 a) // n ungerade, 2 <= a <= n-2

{

u32 d = (n-1) / 2, j = 1;

while (d % 2 == 0)

d /= 2, ++j;

// berechne p = a^d mod n mit der binären Exponentiation:

u64 p = a, q = a;

while (d /= 2) {

q = q * q % n;

if (d % 2) p = p * q % n;

}

if (p == 1 || p == n-1)

return true; // n ist wahrscheinlich prim

while (--j > 0 && p > 1) {

p = p * p % n;

if (p == n-1) return true;

}

return false; // n ist nicht prim

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Praktische_Relevanz">Praktische Relevanz</h2></div>

Primzahltests werden vor allem in der <a href="Kryptographie" title="Kryptographie">Kryptographie</a> benötigt. Ein typisches Beispiel ist die Schlüsselerstellung für das <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA-Kryptosystem</a>, hierfür werden mehrere große Primzahlen benötigt. Zwar wurde im Jahr 2002 mit dem <a href="AKS-Primzahltest" title="AKS-Primzahltest">AKS-Primzahltest</a> erstmals ein beweisbar deterministischer, in polynomialer Zeit laufender Primzahltest vorgestellt. Dessen Laufzeit ist jedoch für praktische Anwendungen meist zu hoch, weswegen für Kryptographie-Software meist immer noch der Miller-Rabin-Test eingesetzt wird. Dabei ist es zwar theoretisch möglich, dass eine zusammengesetzte Zahl als Primzahl genutzt wird, die Wahrscheinlichkeit ist jedoch so gering, dass es in der Praxis keine Rolle spielt.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Johannes_Buchmann" title="Johannes Buchmann">Johannes Buchmann</a>: Einführung in die Kryptographie. 2. Auflage. Springer, 2001, S. 108–111</li>

<li>Karpfinger, Kiechle: Kryptologie, Algebraische Methoden und Algorithmen. Vieweg+Teubner, 2010, S. 147–152, mit vollständigen Beweisen</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a href="Eric_Weisstein" title="Eric Weisstein">Eric W. Weisstein</a>: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Miller-Rabin-Test.</a> In: <a href="MathWorld" title="MathWorld">MathWorld</a> (englisch).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> M. O. Rabin: Probabilistic algorithms. In: J. F. Traub (ed.): Algorithms and complexity. Academic Press 1976, S. 21–39, speziell S. 35/36, zum Teil nach Ideen von Miller

</li>

<li id="cite_note-YAN-2"><a href="#cite_ref-YAN_2-0">↑</a> Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, S. 208–214

</li>

<li id="cite_note-miller-3"><a href="#cite_ref-miller_3-0">↑</a> Gary L. Miller: Riemann’s Hypothesis and Tests for Primality. In: Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Eric Bach: Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, pp. 355–380.

</li>

<li>↑ <a href="Carl_Pomerance" title="Carl Pomerance">Carl Pomerance</a>, <a href="John_L._Selfridge" title="John L. Selfridge">John L. Selfridge</a>, <a href="Samuel_Wagstaff" title="Samuel Wagstaff">Samuel Wagstaff</a>: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The pseudoprimes to 25·10⁹</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></cite>. Band 35, 1980, S. 1003–1026, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090/S0025-5718-1980-0572872-7">10.1090/S0025-5718-1980-0572872-7</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Miller-Rabin-Test&rft.atitle=The+pseudoprimes+to+25%C2%B710%E2%81%B9&rft.au=Carl+Pomerance%2C+John+L.+Selfridge%2C+Samuel+Wagstaff&rft.btitle=Mathematics+of+Computation&rft.date=1980&rft.doi=10.1090%2FS0025-5718-1980-0572872-7&rft.genre=book&rft.pages=1003-1026&rft.volume=35" style="display:none">

<ol class="mw-subreference-list"><li id="cite_note-6"><a href="#cite_ref-6">↑</a> 1023

</li>

</ol></li>

<li>↑ Gerhard Jaeschke: <cite class="lang" lang="en" dir="auto" style="font-style:italic">On strong pseudoprimes to several bases</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></cite>. Band 61, 1993, S. 915–926, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307/2153262">10.2307/2153262</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Miller-Rabin-Test&rft.atitle=On+strong+pseudoprimes+to+several+bases&rft.au=Gerhard+Jaeschke&rft.btitle=Mathematics+of+Computation&rft.date=1993&rft.doi=10.2307%2F2153262&rft.genre=book&rft.pages=915-926&rft.volume=61" style="display:none">

<ol class="mw-subreference-list"><li id="cite_note-8"><a href="#cite_ref-8">↑</a> 926

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> 916

</li>

</ol></li>

<li id="cite_note-Jiang14-10"><a href="#cite_ref-Jiang14_10-0">↑</a> Yupeng Jiang and Yingpu Deng: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Strong pseudoprimes to the first eight prime bases</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></cite>. Band 83, 2014, S. 2915–2924, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090/S0025-5718-2014-02830-5">10.1090/S0025-5718-2014-02830-5</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Miller-Rabin-Test&rft.atitle=Strong+pseudoprimes+to+the+first+eight+prime+bases&rft.au=Yupeng+Jiang+and+Yingpu+Deng&rft.btitle=Mathematics+of+Computation&rft.date=2014&rft.doi=10.1090%2FS0025-5718-2014-02830-5&rft.genre=book&rft.pages=2915-2924&rft.volume=83" style="display:none">

</li>

<li id="cite_note-Sorenson17-11"><a href="#cite_ref-Sorenson17_11-0">↑</a> Jonathan Sorenson, Jonathan Webster: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Strong pseudoprimes to twelve prime bases</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic"><a href="Mathematics_of_Computation" title="Mathematics of Computation">Mathematics of Computation</a></cite>. Band 86, 2017, S. 985–1003, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090/mcom%2F3134">10.1090/mcom/3134</a>, <a href="ArXiv" title="ArXiv">arxiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1509.00864">1509.00864 [math]</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Miller-Rabin-Test&rft.atitle=Strong+pseudoprimes+to+twelve+prime+bases&rft.au=Jonathan+Sorenson%2C+Jonathan+Webster&rft.btitle=Mathematics+of+Computation&rft.date=2017&rft.doi=10.1090%2Fmcom%2F3134&rft.genre=book&rft.pages=985-1003&rft.volume=86" style="display:none">

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> <a rel="nofollow" class="external text" href="https://primes.utm.edu/prove/prove2_3.html">Prime Pages</a> der University of Tennessee at Martin

</li>

<li id="cite_note-13"><a href="#cite_ref-13">↑</a> <a rel="nofollow" class="external text" href="http://miller-rabin.appspot.com/">Miller-Rabin SPRP bases records</a>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">↑</a> Zhenxiang Zhang, Min Tang: Finding strong pseudoprimes to several bases. II. In: Math. Comp. 72 (2003), S. 2085–2097

</li>

<li id="cite_note-15"><a href="#cite_ref-15">↑</a> Die Folge <a rel="nofollow" class="external text" href="https://oeis.org/A014233">A014233</a> in <a href="OEIS" class="mw-redirect" title="OEIS">OEIS</a>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-11-21" href="https://de.wikipedia.org/wiki/?title=Miller-Rabin-Test&oldid=261743713">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>